package class30_Morris遍历.test;

public class Code01_MorrisTraversal {
    public static class Node{
        public int value;
        public Node left;
        public Node right;

        public Node(int i) {
            value = i;
        }
    }

    //Morris基本过程
    public static void morris(Node head){
        if(head == null){
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            if(mostRight!=null){
                while (mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                if(mostRight.right == null){
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }  else {
                    mostRight.right = null;
                }
            }
            cur = cur.right;
        }
    }

    public static void main(String[] args) {
        Node head = new Node(4);
        head.left = new Node(2);
        head.right = new Node(6);
        head.left.left = new Node(1);
        head.left.right = new Node(3);
        head.right.left = new Node(5);
        head.right.right = new Node(7);
    }
}
